package OptimalAlgorithm.SlidingWindow;
//给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
// s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
//例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。
// "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
//返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
//eg:
//输入：s = "barfoothefoobarman", words = ["foo","bar"]
//输出：[0,9]
//解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
//子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
//子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
//输出顺序无关紧要。返回 [9,0] 也是可以的。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class FindSubstring {
/*    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int len = words[0].length();
        int length = words.length;
        if(s.length() < length){
            return list;
        }
        HashMap<String,Integer> hashWord = new HashMap<>();
        for (String word : words) {
            hashWord.put(word, hashWord.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < len; i++) {//right和left出现的位置不同，而产生不同的结果
            HashMap<String,Integer> hashMapS = new HashMap<>();
            for(int right = i,left = i;right <= s.length() - len;right += len){
                //进窗口
                String str = s.substring(right,right + len);
                hashMapS.put(str,hashMapS.getOrDefault(str,0) + 1);
                //判断
                if(right - left + len > length * len){
                    //出窗口
                    String leftsubstring = s.substring(left, left + len);
                    if(hashMapS.get(leftsubstring) == 1){
                        hashMapS.remove(leftsubstring);
                    }else {
                        hashMapS.put(leftsubstring,hashMapS.get(leftsubstring) - 1);
                    }
                    left += len;
                }
                //更新结果
                if(right - left + len > length * len){
                    if(hashMapS.equals(hashWord)){
                        list.add(left);
                    }
                }
            }
        }
        return list;
    }*/
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int wordLen = words[0].length(); // 单个单词的长度
        int wordCount = words.length;    // 单词的数量
        int totalLen = wordLen * wordCount; // 所有单词拼接后的总长度
        int sLen = s.length();

        HashMap<String,Integer> hashWord = new HashMap<>();
        for (String word : words) {
            hashWord.put(word, hashWord.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < wordLen; i++) {//right和left出现的位置不同，而产生不同的结果
            HashMap<String,Integer> hashMapS = new HashMap<>();
            int count = 0;
            for(int right = i,left = i;right <= sLen - wordLen;right += wordLen){
                //进窗口
                String str = s.substring(right,right + wordLen);
                hashMapS.put(str,hashMapS.getOrDefault(str,0) + 1);
                if(hashMapS.get(str) <= (int)hashWord.getOrDefault(str,0)){
                    count++;
                }
                //判断
                if(right - left + wordLen > totalLen){
                    //出窗口
                    String leftsubstring = s.substring(left, left + wordLen);
                    if((int)hashMapS.get(leftsubstring) <= hashWord.getOrDefault(leftsubstring,0)){
                        count--;
                    }
                    if(hashMapS.get(leftsubstring) == 1){
                        hashMapS.remove(leftsubstring);
                    }else {
                        hashMapS.put(leftsubstring,hashMapS.get(leftsubstring) - 1);
                    }
                    left += wordLen;
                }
                //更新结果
                if(count == wordCount){
                        list.add(left);
                }
            }
        }
        return list;
    }
}
